class Solution {
public:
    int m, n;
    vector<vector<int>> dp; // 记忆化缓存

    int uniquePaths(int _m, int _n) {
        m = _m, n = _n;
        dp = vector<vector<int>>(m, vector<int>(n, -1));
        return dfs(0, 0);
    }

    int dfs(int i, int j) {
        // 到达终点，返回1种路径
        if (i == m - 1 && j == n - 1)
            return 1;
        // 越界检查
        if (i >= m || j >= n)
            return 0;
        // 如果已缓存，直接返回结果
        if (dp[i][j] != -1)
            return dp[i][j];

        // 向右走 + 向下走
        int right = dfs(i, j + 1);
        int down = dfs(i + 1, j);

        // 缓存结果并返回
        return dp[i][j] = right + down;
    }
};